package linkedlist.other_1_quicksort;

/**
 * 单链表快速排序交换指针方式
 */
public class QuickSortPointer {
    public static ListNode sortList(ListNode head) {
        return quickSort(head);
    }
    public static ListNode quickSort(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        int pivot = head.val;
        // 将链表拆分成小于pivot部分和大于等于pivot部分
        ListNode small = new ListNode(-1);
        ListNode big = new ListNode(-1);
        ListNode s = small;
        ListNode b = big;
        ListNode cur = head;
        while (cur != null) {
            if (cur.val < pivot) {
                s.next = cur;
                s = s.next;
            } else {
                b.next = cur;
                b = b.next;
            }
            cur = cur.next;
        }
        s.next = big.next;
        b.next = null;
        // 此时以 head 左边都是比 head 小的，右边都是大于等于 head 的，对这两部分 分治
        // head.next 就是右部分的头节点
        ListNode right = quickSort(head.next);
        head.next = null;
        ListNode left = quickSort(small.next);
        // 拼接左右两部分
        cur = left;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = right;
        return left;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(4);
        head.next = new ListNode(2);
        head.next.next = new ListNode(1);
        head.next.next.next = new ListNode(3);
        sortList(head);
    }
}
